iT邦幫忙

2021 iThome 鐵人賽

DAY 21
0

隊列(queue)介紹

隊列就如同堆疊一般,是一種線性表,與堆疊不同的地方在於,堆疊的push和pop操作都是在棧頂(Top)的地方進行操作,而隊列則是插入元素在一端進行,而刪除則是在另外一端執行。

隊列的基本操作為Enqueue(入隊),他是在表的末端(稱為隊尾(rear))插入元素。另一個操作為Dequeue(出隊),作用為刪除(或是回傳)表頭(又稱為(front))的元素。

而元素推入Queue,是遵循著先進先出的原則(First In First Out)。假設我們依序將2和3進行Enqueue,看起來會像是以下

  1. 將2進行Enqueue
  2. 將3進行Enqueue(在隊尾(rear)插入元素)
  3. 進行Dequeue(刪除頭(front)元素)
  4. 進行Dequeue

我們可以觀察到,2為最先進入Queue的元素(Enqueue),也是最先出隊(Enqueue)的元素,也就是所謂First In First Out的特性。

隊列的概念與操作

我們實作隊列無論使用串列還是陣列的方式,對其進行的任何操作皆為https://chart.googleapis.com/chart?cht=tx&chl=O(1),以下為如何使用陣列實作出隊列。

首先,我們需要陣列Queue,以及位置front和rear,他們代表著Queue這個陣列的頭端和末端,除此之外,我們還需要紀錄陣列的大小,也就是陣列中元素的多寡size。所有這一些資訊作為結構(struct)的成員(member)並包裝起來

首先,先針對入隊(Enqueue)進行分析

入隊(Enqueue)


其實我們所進行的事情,就只是改變隊尾(rear = rear + 1),並將元素放入隊尾(Queue[rear] = X),沒有涉及到需要移動到整個陣列的操作,因此,時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(1)。就像是排隊一樣,來的人只要接在原來排隊人群的後面就可以了。

出隊(Dequeue)

接著,針對出隊(Dequeue)進行分析,出隊為將頭(front)元素移除的操作,就像是排隊一樣,排頭的人走了,那其餘的人就必須往前進一格,也因此出隊會涉及到整個陣列的移動,時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(N)

原本排隊情形

排頭的人取得商品後走掉了

後面的人需要跟著往前進一格

以Queue陣列的結構圖演示就如同以下

但出隊需要的時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(N),有沒有辦法將它簡化到https://chart.googleapis.com/chart?cht=tx&chl=O(1),其實是有辦法的,只要我們不要限制隊頭(front)一定要在0號的位置,也就是排頭的位置,就可以不用涉及陣列所有元素移動的操作了,如同下圖所示

為了避免當只有一個元素時,隊頭(front)和隊尾(rear)重合的問題,我們使用兩個指標進行處理,front指標指向Queue陣列的隊頭,==rear指向Queue陣列的隊尾元素的下一個位置==,如下圖所示

執行Dequeue

執行Dequeue

執行Dequeue

我們可以發現,當front和rear重合時,就表示Queue為空的

空間不足的問題,與假溢出(False overflow)問題

下圖為長度為5的陣列,經過入隊(Enqueue)a1,a2,a3,a4的操作後的情況

然後我們將a1,a2出隊(Dequeue)

在將a5入隊(Enqueue)

我們會發現,當我們執行入隊(Enqueue)時,需要將rear + 1,他會跑到陣列界線以外的地方,造成錯誤,而且我們還發現到,當我們要將元素入隊時,如將a6入隊,Queue明明還有0號和1號的位置,卻無法將元素加入,因為會有rear越界的問題,而這個問題,我們稱之為假溢出問題(False overflow)。

解決假溢出問題,使用循環陣列(circular array)

要解決假溢出的問題,其實我們只要將rear跑到陣列界線時,再往下走一格會回到陣列的頭就可以解決了,也就是使陣列的頭尾相接,這種陣列我們稱之為循環陣列(circular array)。

而回到剛剛將a6入隊(Enqueue)的問題,我們使用循環陣列就能夠順利地解決了,原本將a5入隊會發生的狀況使用循環陣列後如下圖所示

然後我們將a6入隊

接著將a7入隊

此時我們又發現新的問題了,前面說過,當front和rear相等時,表示Queue為空的,在單向時行得通,但在循環陣列時就發生問題了,這裡我們的front和rear發生了重合,但是Queue卻不為空,我們要如何解決這個問題?

常見判斷Queue是為滿(Full)還是空(NULL)的方法,front和rear的特殊對應關係

下面我們會介紹常見判斷Queue是空還是滿的方法,歸納上面的演示,由於rear有可能大於front,也有可能小於front,當rear和front只相差一個位置時,有可能是Queue滿(Full)的狀況,但也有可能相差了整整一圈。

我們歸納出了一下結論,如果Queue的最大長度為QueueSize,==則Queue為滿(Full)的條件為https://chart.googleapis.com/chart?cht=tx&chl=(rear%20%2B%201)%20%5C%20mod%5C%20%20%20QueueSize%20%3D%3D%20front,我們已下舉幾個例子來說明 :

Example 1.

如果QueueSize = 5

目前的front = 0,raer = 4
而我們帶入https://chart.googleapis.com/chart?cht=tx&chl=(rear%20%2B%201)%20%5C%20mod%5C%20%20QueueSize%20%3D%3D%20front
https://chart.googleapis.com/chart?cht=tx&chl=(4%20%2B%201)%20%5C%20mod%5C%20%205%20%3D%200,而front恰好為零,符合https://chart.googleapis.com/chart?cht=tx&chl=(rear%20%2B%201)%20%5C%20mod%5C%20%20QueueSize%20%3D%3D%20front
因此判斷此Queue為滿(Full)。P.S:對於Full的Queue,我們保留一個空的格子

Example 2.

如果QueueSize = 5

目前front = 2,rear = 1
而我們帶入https://chart.googleapis.com/chart?cht=tx&chl=(rear%20%2B%201)%20%5C%20mod%5C%20%20QueueSize%20%3D%3D%20front
https://chart.googleapis.com/chart?cht=tx&chl=(1%20%2B%201)%20%5C%20mod%5C%20%205%20%3D%202,而front恰好為2,符合https://chart.googleapis.com/chart?cht=tx&chl=(rear%20%2B%201)%20%5C%20mod%5C%20%20QueueSize%20%3D%3D%20front
因此判斷此Queue為滿(Full)。P.S:對於Full的Queue,我們保留一個空的格子

Example 3.

如果QueueSize = 5

目前front = 2, rear = 0
而我們帶入https://chart.googleapis.com/chart?cht=tx&chl=(rear%20%2B%201)%20%5C%20mod%5C%20%20QueueSize%20%3D%3D%20front
https://chart.googleapis.com/chart?cht=tx&chl=(0%20%2B%201)%20%5C%20mod%5C%20%205%20%3D%201,符合https://chart.googleapis.com/chart?cht=tx&chl=(rear%20%2B%201)%20%5C%20mod%5C%20%20QueueSize%20%3D%3D%20front%20(1%20!%3D%202)
因此判斷Queue未滿。


Queue的長度問題(Queue中元素個數)

我們可以將Queue求長度的問題分為兩個部分進行討論

  1. https://chart.googleapis.com/chart?cht=tx&chl=rear%20%3E%20front時,如下圖

    此時Queue長度為rear - front,4 - 2 = 2

  2. https://chart.googleapis.com/chart?cht=tx&chl=rear%20%3C%20front時,如下圖

    長度的問題就必須分段討論,一個為QueueSize - front,也就是5 - 2,另一段為0 + rear,也就是0 + 1,在將兩者相加,得到Queue的長度。

我們綜合了一下上方兩種情況,得到了一個通用==計算Queue長度的公式
https://chart.googleapis.com/chart?cht=tx&chl=(rear%20-%20front%20%2B%20MaxQueueSize)%5C%20%5C%20mod%20%5C%20MaxQueueSize

取得Queue最後一個元素

取得最後一個元素,我們在實作Queue時,會空出一個格子,而rear指標會指向這一個空格,真正有元素的位置是在rear的前一格(請見上圖),所以我們可能會以為最後一個元素即為Queue[rear - 1],但事實上這是錯的,如果遇到rear在0號位置,那rear - 1即會超出Queue的邊界,造成違法存取的錯誤,因此,我們歸納出了一個公式,用來取得Queue的最後一個元素

Queue最後一個元素: https://chart.googleapis.com/chart?cht=tx&chl=Q-%3Earray%20%5Brear%20-%201%20%2B%20MaxQueueSize%5D%20%5C%20mod%5C%20%20MaxQueueSize

有了這一些結論後,我們就可以開始實作Queue了

單向隊列的實作ADT

下面為使用陣列實作隊列的ADT

#ifndef _Queue_h

Queue* InitQueue(Queue* Q);
void DestroyQueue(Queue* Q);
void ClearQueue(Queue* Q);
int IsEmpty(Queue* Q);
int GetHead(Queue* Q);
int Gettail(Queue* Q);
void EnQueue(Queue* Q, ElementType X);
void DeQueue(Queue* Q);
int QueueLengh(Queue* Q);
void PrintQueue(Queue* Q);
#endif /* _Queue_h */

/* Place in implementation file */
/* Queue implementation is a dynamically allocated array */
#define MaxQueueSize (number)

typedef struct Queue{
    int Front;
    int Rear;
    ElementType *Array;
}Queue;

IsEmpty實作

int IsEmpty(Queue Q)
{
    return QueueLenght(Q) == 0;
}

說明:如果長度為零,表示Queue為空。

IsFull實作

int IsFull(Queue Q)
{
    return QueueLenght(Q) == MaxQueueSize - 1;
}

說明:長度等於MaxQueueSize - 1,原因為Queue狀態為滿時,我們會空出一格。

InitQueue實作

Queue* InitQueue()
{
    Queue* Q = malloc(sizeof(Q));
    Q->array = malloc(sizeof(int) * MaxQueueSize);
    Q->front = 0;
    Q->rear = 0;
    return Q;
}

QueueLengh實作

int QueueLengh(Queue *Q)
{
    return (Q->rear - Q->front + MaxQueueSize) % MaxQueueSize;
}

說明:請參照上方說明。

EnQueue實作

int EnQueue(Queue *Q, int X)
{
    if((Q->rear + 1) % MaxQueueSize == Q->front)
    {
        return -1;
    }
    Q->array[Q->rear] = X;
    Q->rear = (Q->rear + 1) % MaxQueueSize;
    return 0;
}

說明:
https://chart.googleapis.com/chart?cht=tx&chl=(Q-%3Erear%20%2B%201)%20%5C%20mod%5C%20%20MaxQueueSize%20%3D%3D%20Q-%3Efront表示判斷Queue是否為滿,如果發現Queue已滿,則無法再將元素入隊(Enqueue),回傳錯誤碼-1。

如果Queue不為滿,則將元素入隊(Enqueue),也就是將元素加在Queue的尾巴(rear),並改變rear的位置。

DeQueue實作

int DeQueue(Queue* Q)
{
    int front_value;
    if(Q->front == Q->rear)
    {
        return -1;
    }
    front_value = Q->array[Q->front];
    Q->front = (Q->front + 1) % MaxQueueSize;

    return front;
}

說明:
當front和rear相等時,即表示Queue為空(注意: 這是單向Queue,非循環Queue)。

如果Queue不為空,則先將Queue隊頭(front)的元素存入front_value中,並改變front的索引號

之後回傳原先Queue頭元素,也就是front_value。

printQueue實作

void printQueue(Queue *Q)
{
    for(int i = 0; i < QueueLength(Q); i++)
    {
        if(i >= 1)
        {
            printf("%s", "->");
        }
        printf("%d", Q->array[i]);
    }
}

DestroyQueue實作

void DestroyQueue(Queue* Q)
{
    free(Q->array);
    free(Q);
}

GetTail實作

int GetTail(Queue* Q)
{
    return Q->value[Q->rear - 1 + MaxQueueSize] % MaxQueueSize; 
}

Queue實作範例程式碼

#include <stdio.h>
#include <stdlib.h>
#define MaxQueueSize 10

typedef struct Queue{
    int front;
    int rear;
    int *array;
}Queue;

Queue* InitQueue(void);
void DestroyQueue(Queue* Q);
void ClearQueue(Queue* Q);
int IsEmpty(Queue* Q);
int IsFull(Queue* Q);
int GetHead(Queue* Q);
int GetTail(Queue* Q);
int EnQueue(Queue* Q, int X);
int DeQueue(Queue* Q);
int QueueLength(Queue* Q);
void printQueue(Queue* Q);

int main(void)
{
    Queue *Q = InitQueue();
    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    DeQueue(Q);
    DeQueue(Q);
    DeQueue(Q);
    printQueue(Q);
    printf("\nThe QueueLength is %d", QueueLength(Q));
    printf("\nThe front of Queue is %d", GetHead(Q));

    DestroyQueue(Q);
}

Queue* InitQueue()
{
    Queue* Q = malloc(sizeof(Q));
    Q->array = malloc(sizeof(int) * MaxQueueSize);
    Q->front = 0;
    Q->rear = 0;
    return Q;
}

void DestroyQueue(Queue* Q)
{
    free(Q->array);
    free(Q);
}

int QueueLength(Queue *Q)
{
    return (Q->rear - Q->front + MaxQueueSize) % MaxQueueSize;
}

int EnQueue(Queue *Q, int X)
{
    if((Q->rear + 1) % MaxQueueSize == Q->front)
    {
        return -1;
    }
    Q->array[Q->rear] = X;
    Q->rear = (Q->rear + 1) % MaxQueueSize;
    return 0;
}

int DeQueue(Queue* Q)
{
    int front;
    if(Q->front == Q->rear)
    {
        return -1;
    }
    front = Q->array[Q->front];
    Q->front = (Q->front + 1) % MaxQueueSize;

    return front;
}

void printQueue(Queue *Q)
{
    for(int i = Q->front; i < Q->rear; i++)
    {
        if(i > Q->front)
        {
            printf("%s", "->");
        }
        printf("%d", Q->array[i]);
    }
}

int IsEmpty(Queue *Q)
{
    return QueueLength(Q) == 0;
}

int IsFull(Queue *Q)
{
    return QueueLength(Q) == MaxQueueSize - 1;
}

int GetHead(Queue *Q)
{
    return Q->array[Q->front];
}

int GetTail(Queue* Q)
{
    return Q->value[(Q->rear - 1 + MaxQueueSize) % MaxQueueSize]; 
}

參考資料: 大話數據結構,C语言程序设计现代方法第2版,Introduction to algorithms 3rd,圖片源於網路(flaticon)


上一篇
Day-20 堆疊(Stack)
下一篇
Day-22 樹(Tree), 二元搜尋樹(Binary Search Tree)
系列文
從0開始啃Introduction of algorithms心得與記錄30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言